package com.zang.tree;

import com.zang.linkedlist.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZVerify
 * @since 2022/10/30 16:41
 * @see <a href="https://leetcode.cn/problems/invert-binary-tree/description/">...</a>
 **/
public class 翻转二叉树 {
    public TreeNode invertTree(TreeNode root) {
        if (root==null) return null; // 如果为null直接返回
        Deque<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        // 广度优先，如果队列里边还有节点说明没转换完
        while (!linkedList.isEmpty()){
            for (int i = 0; i < linkedList.size(); i++) {
                TreeNode first = linkedList.pollFirst();
                // 先将子树进行转换然后添加完成其整颗树的翻转
                swap(first);
                if (first.left!=null) linkedList.offer(first.left);
                if (first.right!=null) linkedList.offer(first.right);
            }
        }
        return root;
    }

    private void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}
